This invention relates to the identification of regions, or objects of interest, in images. The term "image segmentation" refers to the process of identifying regions, or objects of interest, in pictures or images. For example, in a photograph depicting a vacation, potentially desirable segmentations would identify any or all forms of a person, a dog, a frisbee, a tree, and the like. Many methods for performing image segmentations have been developed, ranging from "fuzzy" methods based on theories from the field of artificial intelligence, to mathematically sophisticated methods involving intensity spectra and polynomial fitting.
Generally, segmentation methods fall into one of two categories, namely, fully-automatic segmentation and semi-automatic segmentation. Fully-automatic segmentation methods do not require any human input to perform their task, whereas semi-automatic segmentation methods require minimal help from a human. Segmentation methods may also be classified as wide-ranging or narrow-ranging, where wide-ranging methods are designed to detect many different types of regions or objects, while narrow-ranging methods are specific to a particular task.
Many schemes have been proposed for image segmentation. U.S. Pat. No. 5,048,095 issued to Bir et al. discusses a method of segmentation using a genetic algorithm. The genetic algorithm searches for a collection of parameters that allow an accompanying image segmenter to perform successfully. However, the outcome of the segmentation thus depends on the quality of the image segmenter, and the nature and design of the segmenter is not specified in the reference. Thus, the patent really begs the question of how to perform image segmentation.
U.S. Pat. Nos. 5,458,126 and 5,433,199, issued to Cline et al. discuss a method of identifying cardiac chambers using bivariate statistical distributions that are based on gradients or magnitudes of spatial changes in the images under consideration. The distributions are used to connect pixels together into presumed collections of identical tissue. This method is necessarily highly sensitive to noise and image imperfections, and is specific to the cardiac domain.
An article entitled "Snakes: Active contour models," International Journal of Computer Vision, pp. 321-331, 1988, by Kass, Witkin, and Terzopoulos, discloses a method that models contours as continuity-constrained spline curves with concomitant energy terms. These curves are called "active contours" or often "snakes." The active contour presumably fits a target border best when the energy terms are minimized. However, active contours are generally highly sensitive to initial conditions, parameters, and the particular energy minimization algorithms used. In addition, active contours do not work well in situations where spline curves do not function well, for example, where sharp corners exist.
U.S. Pat. No. 5,239,591 issued to Ranganath discusses a method for using propagated "seed contours" to segment the endocardial border. This method, based on active contours, suffers from all of the drawbacks described in the previous paragraph. Furthermore, the endocardial border problem is not a particularly challenging problem for known methods of segmentation, since it typically shows very high contrast.
An article entitled "Shape Modeling with Front Propagation: A Level Set Approach," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 17, No 2, February 1995, by Sethian, Malladi, and Vemuri discloses using a closed hypersurface .psi. to model shapes; that is, the shape of a target object at some point in time corresponds to a curve .psi.=0. This method is computationally expensive, embodies a number of limiting assumptions (most importantly, that the shape in question can be modeled as a propagating solid/liquid interface), and is highly sensitive to parameters.
R. P. Grzeszczuk and D. N. Levin, in an article entitled, "`Brownian Strings`: Segmenting Images with Stochastically Deformable Contours," IEEE Trans on PAMI, Vol. 19, 1100-1114 (1997) describe the use of simulated annealing on a contour described by inter-pixel cracks, rather than active contours. This method suffers from sensitivity to particular energy terms, and parameters, such as temperature and annealing time, and because it seeks a global energy minimum, it is easily led astray.
All prior art methods of image segmentation methods suffer from one of more of the following disadvantages such as:
a) known methods may rely on purely statistical information, and devalue geometric or domain knowledge; PA1 b) known methods may rely on global information, and devalue regional variation in a target or its outline; PA1 c) known methods may seek a global energy minimum, which is an inherently non-robust and an error-prone process; PA1 d) known methods may use mathematically sophisticated algorithms that are sensitive to image quality, noise, parameters, etc., and which require large amounts of calculation time; PA1 e) known methods may use poor or poorly optimized algorithms; PA1 f) known methods may be restricted to particular problem domains, or to "toy" problems which have little or no practical value; PA1 g) known methods may use mathematical models which have no relation to the problem being attacked (i.e. balloons, splines, liquid/solid interfaces). PA1 a) it is applicable to many different problem domains, as opposed to other known methods which work only for certain applications, or under highly restricted conditions. PA1 b) it does not rely on high-precision or mathematically complicated techniques, such as polynomial fitting, global energy minimization, probability distributions, and the like. Therefore it is not easily fooled by factors such as noise or local pixel intensity irregularities, which are fatal to other known methods. PA1 c) it runs very quickly because it relies mainly on integer rather than floating-point arithmetic, and utilizes efficient and optimized routines. PA1 d) it may simultaneously utilize different types of information (statistical, geometric, a priori, etc.), both locally and globally. PA1 e) it does not use artificial and limiting shape models, such as snakes or level sets. PA1 f) it functions well with real world problems. PA1 g) its accuracy is easily improved by providing it with additional training contours.
Accordingly, it is an object of the present invention to provide a novel apparatus and method for segmenting images to substantially overcome the above-described problems.
It is an object of the present inventive method to provide a method and apparatus of image segmentation (a "segmenter") that employs a combination of image intensity information, user-supplied information, and a priori domain knowledge information particular to the type of problem at hand, to segment images with a high degree of accuracy.
It is another object of the present inventive method to provide an image segmenter that minimizes the requisite amounts of user-supplied and a priori information.
It is a further object of the present inventive method to provide an image segmenter that is easily modified to operate successfully on many problems and domains, and which minimizes the amount of time and effort to enact such modifications.
It is also an object of the present inventive method to provide an image segmenter that operates extremely quickly and is computationally efficient.